#pragma once

#include <boost/foreach.hpp>

#include <list>
#include <stack>




namespace boostext
{
	#define TYPEDEF_TREE( tree )	




	/**
	 * @brief   This functor implements operator== in a way, so that it can be used in conjunction with
	 *          tree_list.
	 *
	 * This class simply stores a value to compare against (defined on construction).
	 */
	template
	<
		class _Ty
	>
	class equal_predicate
	{
	private:

		/// The value to compare against
		_Ty _val;

	public:

		/**
		 * Create an equal_predicate.
		 *
		 * @param _Val   the value to compare against
		 */
		equal_predicate(const _Ty& _Val)
			: _val(_Val)
		{}



		/**
		 * Compare the stored value against another one.
		 */
		bool operator()(const _Ty& _Val)
		{
			return _val == _Val;
		}
	};
	////////////////////////////////////////////////////////////////////////////////////////////////

	/**
	 * @brief   This class implements a thin wrapper around an arbitrary unary predicate.
	 *
	 * When invoked, the wrapper passes the return value of tree_node::get() into the actual predicate,
	 * which may be equal_predicate for example. This class is necessary, because a tree_node does not
	 * store a list of the actual value type, but a list of nodes (of which each stores one value). To
	 * the user, it seems as if the tree simply stores a list of values, because this wrapper is
	 * applied to any unary predicate.
	 */
	template
	<
		class _Tree_Container,
		class _Predicate
	>
	class tree_unary_predicate_wrapper
	{
	public:

		/// Typedef for a tree_node
		typedef _Tree_Container   tree_node;

	private:

		/// The predicate we wrap around and supply with elements
		_Predicate _pred;

	public:

		/**
		 * Create a new tree_unary_predicate_wrapper from a custom predicate.
		 */
		tree_unary_predicate_wrapper(const _Predicate& _Pred)
			: _pred(_Pred)
		{}

		/**
		 * Compare the tree_node using the supplied predicate, which
		 * calls the predicate with the value, stored in the given node.
		 */
		bool operator()(const tree_node& _node)
		{
			return _pred(_node.get());
		}
	};
	////////////////////////////////////////////////////////////////////////////////////////////////




	/**
	 * @brief   This functor implements operator< in a way, so that it can be used in conjunction with
	 *          tree_list.
	 *
	 * This class simply compares two values, using operator< internally.
	 */
	template
	<
		class _Ty
	>
	class smaller_operator
	{
	public:

		/**
		 * Compare two values.
		 * Equivalent to _Left < _Right.
		 */
		bool operator()(const _Ty& _Left, const _Ty& _Right)
		{
			return _Left < _Right;
		}
	};
	////////////////////////////////////////////////////////////////////////////////////////////////

	/**
	 * @brief   This class implements a thin wrapper around an arbitrary binary predicate.
	 *
	 * When invoked, the wrapper passes the return value of tree_node::get() into the actual predicate,
	 * which may be smaller_operator for example. This class is necessary, because a tree_node does not
	 * store a list of the actual value type, but a list of nodes (of which each stores one value). To
	 * the user, it seems as if the tree simply stores a list of values, because this wrapper is
	 * applied to any binary predicate.
	 */
	template
	<
		class _Tree_Container,
		class _Compare
	>
	class tree_binary_compare_wrapper
	{
	public:

		/// Typedef for a tree_node
		typedef _Tree_Container   tree_node;

	private:

		/// The predicate we wrap around and supply with elements
		_Compare _pred;

	public:

		/**
		* Create a new tree_unary_predicate_wrapper from a custom predicate.
		*/
		tree_binary_compare_wrapper(const _Compare& _Pred)
			: _pred(_Pred)
		{}

		/**
		* Compare the tree_nodes using the supplied predicate, which
		* calls the predicate, using the values of both given nodes.
		*/
		bool operator()(const tree_node& _Left, const tree_node& _Right)
		{
			return _pred(_Left.get(), _Right.get());
		}
	};
	////////////////////////////////////////////////////////////////////////////////////////////////




	/**
	 * Sort a tree using the binary predicate smaller_operator.
	 *
	 * @note      this function works recursively
	 */
	template <class _Tree_Container>
	void tree_sort(_Tree_Container& _That)
	{
		// Sort our childs
		tree_sort(_That, smaller_operator<_Tree_Container::_Ty>());

		// Tell our childs to sort theirs as well
		BOOST_FOREACH(_Tree_Container& child, _That)
		{
			tree_sort(child);
		}
	}
	////////////////////////////////////////////////////////////////////////////////////////////////

	/**
	 * Sort a tree using a custom supplied binary predicate
	 *
	 * @note     this function works recursively
	 */
	template
	<
		class _Tree_Container,
		class _Compare
	>
	void tree_sort(_Tree_Container& _That, _Compare _comp)
	{
		// Sort our childs
		std::sort(_That.begin(), _That.end(), tree_binary_compare_wrapper<_Tree_Container,_Compare>(_comp));

		// Tell our childs to sort theirs as well
		BOOST_FOREACH(_Tree_Container& child, _That)
		{
			tree_sort(child, _comp);
		}
	}
	////////////////////////////////////////////////////////////////////////////////////////////////




	/**
	 * @brief   This class implements a tree.
	 *
	 * It uses a std::list as the underlying storage and can store an arbitrary
	 * number of levels.
	 *
	 * @todo   create a flat_iterator to iterate over the entire subtree at once
	 * @todo   create a depth_iterator to iterate over the entire subtree at once
	 */
	template
	<
		class _Ty, //< The actual type of the value this tree stores
		template<class,class> class _Container = std::list, //< The container we want to use as the underlying storage
		template<class> class _Ax = std::allocator //< The allocator used by the container
	>
	class tree_list
	{
	public:

		/// Stored value's type
		typedef typename _Ty                                 _Ty;
		/// Typedef for a tree_list, using the same value-type, container and allocator
		typedef typename tree_list<_Ty,_Container,_Ax>       tree_node;
		/// Typedef for the allocator
		typedef typename _Ax<tree_node>                      allocator;
		/// Typedef for the underlying storage container
		typedef typename _Container<tree_node,allocator>     container;
		/// Typedef for a type, describing sizes
		typedef typename container::size_type                size_type;
		/// Typedef for a mutable iterator
		typedef typename container::iterator                 iterator;
		/// Typedef for a non-mutable iterator
		typedef typename container::const_iterator           const_iterator;
		/// Typedef for a reverse ordered mutable iterator
		typedef typename container::reverse_iterator         reverse_iterator;
		/// Typedef for a reverse ordered non-mutable iterator
		typedef typename container::const_reverse_iterator   const_reverse_iterator;

	public:

		/**
		 * @brief   This iterator can be used to iterate over the entire tree_list in one go,
		 *          instead of manually building a recursive loop.
		 *
		 * The const_depth_iterator offers the same syntactic interface as std::list::const_iterator, but
		 * it iterates over the entire tree, preferring depth nodes. It travels an entire branch, before going up
		 * and evaluating the next one.
		 *
		 * Internally, const_depth_iterator manages a stack that defines the current active branch of the iterator.
		 * When incremented, this iterator either increases the iterator of the current node (the topmost) of
		 * the stack or (when the current node has no more child-nodes) travels the stack upwards until there is
		 * it finds a next node.
		 * Uses the same runtime checks as an SC++L iterator.
		 */
		class const_depth_iterator
		{
		public:

			/// Typedef for a const_depth_iterator (this exact type)
			typedef const_depth_iterator                         _Myt_iter;

			/// Typedef for a tree_node => const_iterator pair
			typedef std::pair<const tree_node*,const_iterator>   _Pos;
			/// Stack of _Pos pairs
			typedef std::stack<_Pos>                             _PosStack;

		private:

			/// Stack that defines the current branch, taken by the iterator
			_PosStack   _stack;

		private:

			/**
			 * Create a const depth iterator from the given iterator and node.
			 */
			const_depth_iterator(const_iterator _it, const tree_node* _Node)
			{
				_stack << _Pos(_it, _Node);
			}

		public:

			/**
			 * Create an empty const_depth_iterator.
			 */
			const_depth_iterator()
			{}


			/**
			 * Get a reference to the value at the current position.
			 */
			const _Ty& operator*() const
			{
				return *_stack.top().second;
			}

			/**
			 * Get a reference to the value at the current position.
			 */
			const _Ty& operator->() const
			{
				return *_stack.top().second;
			}



			/**
			 * Pre-increment operator.
			 */
			_Myt_iter& operator++()
			{
				_Pos& cur = _stack.top();
				const tree_node* node = cur.first;
				const_iterator&  it   = cur.second;

				if( it != node->end() )
				{
					// When this node still has child-nodes, then increment the iterator on
					// the current node
					++it;
				}
				else
				{
					// The current node ran out of child-nodes
					// We have to travel to this node's parent node, get the next node there
					#if _HAS_ITERATOR_DEBUGGING
						if( !(_stack.size() > 1) )
						{
							_DEBUG_ERROR("depth tree iterator not incrementable");
							_SCL_SECURE_TRAITS_OUT_OF_RANGE;
						}
					#else
						_SCL_SECURE_VALIDATE_RANGE( _stack.size() > 1 );
					#endif

					_stack.pop();

					// Do the game once more
					return ++(*this);
				}

				return *this;
			}

			/**
			 * Pre-decrement operator
			 */
			_Myt_iter& operator--()
			{
				_Pos& cur = _stack.top();
				const tree_node* node = cur.first;
				const_iterator&  it   = cur.second;

				if( it != node->begin() )
				{
					// When this node still has child-nodes, then decrement the iterator on
					// the current node
					 --it;
					return *this;
				}
				else
				{
					// The current node ran out of child-nodes
					// We have to travel to this node's parent node, get the previous node there
					#if _HAS_ITERATOR_DEBUGGING
						if( !(_stack.size() > 1) )
						{
							_DEBUG_ERROR("depth tree iterator not incrementable");
							_SCL_SECURE_TRAITS_OUT_OF_RANGE;
						}
					#else
						_SCL_SECURE_VALIDATE_RANGE( _stack.size() > 1 );
					#endif

					_stack.pop();

					// Do the game once more
					return --(*this);
				}
			}



			/**
			 * Post increment operator.
			 */
			_Myt_iter operator++(int)
			{
				_Myt_iter _Tmp = *this;
				++*this;
				return _Tmp;
			}

			/**
			 * Post decrement operator.
			 */
			_Myt_iter operator--(int)
			{
				_Myt_iter _Tmp = *this;
				--*this;
				return _Tmp;
			}
		};
		/////////////////////////////////////////////////////////////////////////////////////////////

	private:

		/// The actual storage container with child nodes (if any)
		container   _children;
		/// The value of this node
		_Ty         _val;

	public:

		/**
		 * Create an empty tree_list.
		 */
		tree_list()
		{}

		/**
		 * Create a tree_list from a value
		 */
		explicit tree_list(const _Ty& _Val)
			: _val(_Val)
		{}

		/**
		 * Create a tree_list from a range of elements.
		 *
		 * @param _Val     The value of this node
		 * @param _First   The position of the first node in the range of elements to be copied
		 * @param _Last    The position of the first node beyond the range of elements to be copied
		 */
		template <class _Iter>
		tree_list(const _Ty& _Val, _Iter _First, _Iter _Last)
			: _children(_First, _Last)
			, _val(_Val)
		{}

		/**
		 * Create a tree_list of the specified size.
		 * The value of this node is being default constructed while those nodes are added as children.
		 *
		 * @param _Size   The size of the tree_list
		 * @param _Val    The value of new elements added to the tree_list if the new size is larger that the original size. If the value is omitted, the new objects are assigned the default value.
		 */
		tree_list(size_type _Size, const _Ty& _Val)
			: _children(_Size, tree_node(_Val))
			, _val()
		{}

		/**
		 * Destroy a tree_list.
		 */
		~tree_list()
		{}



		/**
		 * Get the value of this node.
		 */
		_Ty& get()
		{
			return _val;
		}

		/**
		 * Get the value of this node.
		 */
		const _Ty& get() const
		{
			return _val;
		}

		/**
		 * Get the value of this node.
		 */
		operator _Ty& ()
		{
			return _val;
		}

		/**
		 * Get the value of this node.
		 */
		operator const _Ty& () const
		{
			return _val;
		}



		/**
		 * Assign another tree_list to this one.
		 *
		 * @param _That   node to copy
		 */
		tree_node &operator = (const tree_node& _That)
		{
			_children = _That._children;
			_val      = _That._val;

			return *this;
		}

		/**
		 * Assign another value to this node.
		 *
		 * @param _Val   value to assign
		 */
		tree_node &operator = (const _Ty& _Val)
		{
			_val = _Val;

			return *this;
		}



		/**
		 * Erase the tree_list and copy the specified elements to the empty tree_list.
		 * This function does \b not modify the value of this node.
		 *
		 * @param _First   The position of the first element in the range of elements to be copied
		 * @param _Last    The position of the first element beyond the range of elements to be copied
		 */
		template <class _Iter>
		void assign(_Iter _First, _Iter _Last)
		{
			_children.assign(_First, _Last);
		}

		/**
		 * Erase the tree_list and copy the specified node to the empty tree_list.
		 * This function does \b not modify the value of this node.
		 *
		 * @param _Count   The number of nodes being inserted into the tree_list
		 * @param _Val     The value of the nodes being inserted into the tree_list
		 */
		void assign(size_type _Count, const _Ty& _Val)
		{
			// Since we wrap around _Elem, we insert a tree that constructs from that _Elem
			_children.assign(_Count, tree_node(_Val));
		}



		/**
		 * Get a reference to the last node of the tree_list.
		 */
		tree_node &back()
		{
			return _children.back();
		}

		/**
		 * Get a reference to the last node of the tree_list.
		 */
		const tree_node &back() const
		{
			return _children.back();
		}



		/**
		 * Get a random-access iterator to the first node in the tree_list.
		 */
		iterator begin()
		{
			return _children.begin();
		}

		/**
		 * Get a random-access iterator to the first node in the tree_list.
		 */
		const_iterator begin() const
		{
			return _children.begin();
		}



		/**
		 * Erase the nodes of the tree_list.
		 */
		void clear()
		{
			_children.clear();
		}



		/**
		 * Test if the tree_list is empty.
		 */
		bool empty() const
		{
			return _children.empty();
		}


		/**
		 * Get a random-access iterator that points just beyond the end of the tree_list.
		 */
		iterator end()
		{
			return _children.end();
		}

		/**
		 * Get a random-access iterator that points just beyond the end of the tree_list.
		 */
		const_iterator end() const
		{
			return _children.end();
		}



		/**
		 * Remove a node from the tree_list
		 *
		 * @param _Where   Position of the element to be removed from the tree_list
		 */
		iterator erase(const_iterator _Where)
		{
			return _children.erase(_Where);
		}

		/**
		 * Remove a range of elements from the tree_list
		 *
		 * @param _First   Position of the first element removed from the tree_list
		 * @param _Last    Position just beyond the last element removed from the tree_list
		 */
		iterator erase(const_iterator _First, const_iterator _Last)
		{
			return _children.erase(_First, _Last);
		}



		/**
		 * Get a reference to the first node of the tree_list.
		 */
		tree_node& front()
		{
			return _children.front();
		}


		/**
		 * Get a reference to the first node of the tree_list.
		 */
		const tree_node& front() const
		{
			return _children.front();
		}



		/**
		 * Insert a value into the tree_list at the specified position.
		 *
		 * @param _Where   The position in the tree_list where the first element is inserted
		 * @param _Val     The value of the node being inserted into the tree_list
		 */
		void insert(const_iterator _Where, const _Ty& _Val)
		{
			_children.insert(_Where, tree_node(_Val));
		}

		/**
		 * Insert a tree_list into the tree_list at the specified position.
		 *
		 * @param _Where   The position in the tree_list where the first element is inserted
		 * @param _Node    The node being inserted into the tree_list
		 */
		void insert(const_iterator _Where, const tree_node &_Node)
		{
			_children.insert(_Where, _Node);
		}

		/**
		 * Insert a number of values into the tree_list at the specified position.
		 *
		 * @param _Where   The position in the tree_list where the first element is inserted
		 * @param _Count   The number of values being inserted into the tree_list
		 * @param _Val     The value of the node being inserted into the tree_list
		 */
		void insert(const_iterator _Where, size_type _Count, const _Ty& _Val)
		{
			_children.insert(_Where, _Count, tree_node(_Val));
		}

		/**
		 * Insert a number of nodes into the tree_list at the specified position.
		 *
		 * @param _Where   The position in the tree_list where the first element is inserted
		 * @param _Count   The number of nodes being inserted into the tree_list
		 * @param _Node    The node being inserted into the tree_list
		 */
		void insert(const_iterator _Where, size_type _Count, const tree_node& _Node)
		{
			_children.insert(_Where, _Count, _Node );
		}

		/**
		 * Insert a number of nodes into the tree_list at the specified position.
		 *
		 * @param _Where   The position in the tree_list where the first node is inserted
		 * @param _First   The position of the first node in the range of elements to be copied
		 * @param _Last    The position of the first node beyond the range of elements to be copied
		 */
		template <class _Iter>
		void insert(const_iterator _Where, _Iter _First, _Iter _Last)
		{
			_children.insert(_Where, _First, _Last);
		}

		/**
		 * Get the maximum length of the tree_list.
		 */
		size_type max_size() const
		{
			return _children.max_size();
		}

		/**
		 * Get the number of nodes in this tree_list.
		 */
		size_type size() const
		{
			return _children.size();
		}



		/**
		 * Delete the node at the beginning of the tree_list.
		 */
		void pop_front()
		{
			_children.pop_front();
		}

		/**
		 * Delete the node at the end of the tree_list.
		 */
		void pop_back()
		{
			_children.pop_back();
		}



		/**
		 * Add a value to the end of the tree_list.
		 *
		 * @param _Val   The value added to the end of the tree_list.
		 */
		void push_back(const _Ty& _Val)
		{
			_children.push_back(tree_node(_Val));
		}

		/**
		 * Add a node to the end of the tree_list.
		 *
		 * @param _Node   The node added to the end of the tree_list.
		 */
		void push_back(const tree_node& _Node)
		{
			_children.push_back(_Node);
		}



		/**
		 * Add a value to the beginning of the tree_list.
		 *
		 * @param _Val   The value added to the beginning of the tree_list.
		 */
		void push_front(const _Ty& _Val)
		{
			_children.push_front(tree_node(_Val ));
		}

		/**
		 * Add a node to the beginning of the tree_list.
		 *
		 * @param _Node   The node added to the beginning of the tree_list.
		 */
		void push_front(const tree_node& _Node)
		{
			_children.push_front(_Node);
		}



		/**
		 * Erase nodes in the tree_list that match a specified value.
		 * @note   this function works recursively
		 *
		 * @param _Val   The value which, if held by an node, will result in that node's removal from the tree_list
		 */
		void remove(const _Ty& _Val)
		{
			equal_predicate<_Ty> _pred(_Val);

			// Now remove every child that stores such a value
			remove_if(_pred);

			// There could still be sub-elements that store such a value, so we walk through those
			// as well (that's the recursion)
			BOOST_FOREACH(tree_node& child, _children)
			{
				child.remove_if(_pred);
			}
		}

		/**
		 * Erase nodes from the tree_list for which a specified predicate is satisfied.
		 * @note   this function works recursively
		 *
		* @param _pred   The unary predicate which, if satisfied by a node, results in the deletion of that node from the tree_list.
		 */
		template <class Predicate>
		void remove_if(Predicate _pred)
		{
			_children.remove_if(_pred);

			// There could still be sub-elements that match the predicate, so we walk through those
			// as well (that's the recursion)
			BOOST_FOREACH(tree_node& child, _children)
			{
				child.remove_if(_pred);
			}
		}



		/**
		 * Get an iterator to the first node in a reversed tree_list.
		 */
		reverse_iterator rbegin()
		{
			return _children.rbegin();
		}

		/**
		 * Get an iterator to the end of a reversed tree_list.
		 */
		reverse_iterator rend()
		{
			return _children.rend();
		}



		/**
		 * Get an iterator to the first node in a reversed tree_list.
		 */
		const_reverse_iterator rbegin() const
		{
			return _children.rbegin();
		}

		/**
		 * Get an iterator to the end of a reversed tree_list.
		 */
		const_reverse_iterator rend() const
		{
			return _children.rend();
		}

		/**
		 * Reserve a minimum length of storage for a tree_list object, allocating space if necessary.
		 *
		 * @param _count   The minimum length of storage to be allocated for the tree_list
		 */
		void reserve(size_type _count)
		{
			_children.reserve(_count);
		}



		/**
		 * Specify a new size for the tree_list.
		 *
		 * @param _Newsize   The new size of the tree_list
		 */
		void resize(size_type _Newsize)
		{
			_children.resize(_Newsize);
		}

		/**
		 * Specify a new size for the tree_list.
		 *
		 * @param _Newsize   The new size of the tree_list
		 * @param _Val       The value of new nodes added to the tree_list if the new size is larger that the original size. If the value is omitted, the new objects are assigned the default value.
		 */
		void resize(size_type _Newsize, const _Ty& _Val)
		{
			_children.resize(_Newsize, tree_node(_Val));
		}



		/**
		 * Reverse the order in which the elements occur in the tree_list.
		 */
		void reverse()
		{
			_children.reverse();
		}



		/**
		 * Remove all elements from this tree_list and insert them before the element located at _where in the target tree_list.
		 *
		 * @param _Where   The position in the target shared_list before which the elements of this tree_list are to be inserted
		 * @param _That    The argument tree_list that is to be inserted into the target list
		 */
		void splice(iterator _Where, tree_node& _That)
		{
			_children.splice(_Where, _That._children);
		}

		/**
		 * Remove the element pointed to by _first in this tree_list and insert it before the element in the target tree_list pointed to by _where.
		 *
		 * @param _Where   The position in the target shared_list before which the elements of this tree_list are to be inserted
		 * @param _That    The argument shared_list that is to be inserted into the target list
		 * @param _First   The element to be removed from this tree_list and inserted into the target tree_list
		 */
		void splice(iterator _Where, tree_node& _That, iterator _First)
		{
			_children.splice(_Where, _That._children, _First);
		}

		/**
		 * Remove the range of elements designated by [_first, _last] from this tree_list and insert them before the element in the target tree_list pointed to by _where.
		 *
		 * @param _Where   The position in the target tree_list before which the elements of this tree_list are to be inserted
		 * @param _That    The argument tree_list that is to be inserted into the target list
		 * @param _First   The element to be removed from this tree_list and inserted into the target tree_list
		 * @param _Last    The first element beyond the range to be inserted from this tree_list
		 */
		void splice(iterator _Where, tree_node& _That, iterator _First, iterator _Last)
		{
			_children.splice(_Where, _That.d.get(), _First, _Last);
		}



		/**
		 * Arranges the elements of the tree_list in ascending order.
		 * @note   this function works recursively
		 */
		void sort()
		{
			// We use the smaller_operator as the standard sorting algorithm
			sort(smaller_operator<_Ty>());

			BOOST_FOREACH(tree_node& child, _children)
			{
				child.sort();
			}
		}

		/**
		 * Arranges the elements in the tree_list with respect to some user-specified order relation.
		 * @note   this function works recursively
		 */
		template <class _Compare>
		void sort(_Compare _Comp)
		{
			_children.sort(tree_binary_compare_wrapper<tree_node,_Compare>(_Comp));

			BOOST_FOREACH(tree_node& child, _children)
			{
				child.sort(_Comp);
			}
		}



		/**
		 * Swap this tree_list with another one.
		 */
		void swap(tree_node& _That)
		{
			std::swap(_children, _That._children);
			std::swap(_val, _That._val);
		}



		/**
		 * Remove adjacent duplicate elements from the tree_list.
		 */
		void unique()
		{
			_children.unique();
		}

		/**
		 * Remove adjacent elements that satisfy some other binary predicate from the tree_list.
		 *
		 * @param _pred   The binary predicate used to compare successive elements
		 */
		template <class _BinaryPredicate>
		void unique(_BinaryPredicate _pred)
		{
			_children.unique(_pred);
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////////////////////////////
